leetcode 1055.形成字符串的最短路经

解题思路

1. 以target字符串为基准，从index=0开始与souce[i]比较，如果相同，source和target的index向后；如果不相同，source的下一个字符直至source结束；
2. 上一步完成后，可能source和target一个字符都没有匹配上，或者至少匹配上一个；判断一下如果一个都没有匹配上，肯定就直接返回-1了；如果至少匹配上一个，那就继续比较。

复杂度分析

• 时间复杂度： O(n^2)
• 空间复杂度： O(1)

代码

int shortestWay(char * source, char * target){
    int cnt = 0;  
    int t_index = 0;
    while (t_index < strlen(target)) {
        int tmp = t_index;
        for (int i = 0; i < strlen(source); i++) {
            if (source[i] == target[t_index]) {
                t_index++;
                continue;
            }
        }
        if (tmp != t_index) {
            cnt++;
            continue;
        } else {
            return -1;
        }
    }
    return cnt;
}